package 找树左下角的值;

import java.util.ArrayDeque;

public class Solution {
    // 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
    public int findBottomLeftValue(TreeNode root) {
        // 采用层序遍历
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        // 记录当前层次二叉树的 最底层 最左边 节点的值
        int lowerLeftValue = root.val;
        // 记录当前层次最右边的一个节点
        TreeNode levelLastNode = root;
        while (!queue.isEmpty()) {
            // 取出一个节点，并将其下一层的左右孩子入队
            TreeNode p = queue.poll();
            if (p.left != null) queue.offer(p.left);
            if (p.right != null) queue.offer(p.right);
            // 如果当前节点是当前层次的最后一个节点，需要更新levelLastNode为下一层的最右节点，
            // 且需要更新lowerLeftValue为下一层的最左边节点值
            if (p == levelLastNode && !queue.isEmpty()) {
                levelLastNode = queue.peekLast();
                lowerLeftValue = queue.peekFirst().val;
            }
        }
        return lowerLeftValue;
    }
}
